#include <iostream>
#include <vector>
#include <unordered_set>

struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
	
};

class Solution1 {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head || !(head->next)) return nullptr;
        ListNode node = ListNode(-1, head);
        ListNode* fast = &node;
        ListNode* slow = &node;
        ++n;
        while (fast && n--)
            fast = fast->next;
        while (fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return node.next;
    }
};

class Solution2 {
public:
    int numberOfAlternatingGroups(vector<int>& colors) {
        int cnt = 0; int n = colors.size();
        for (int i = 0; i < n; ++i)
        {
            int left = (i + n - 1) % n; int right = (i + 1) % n;
            if (colors[i] != colors[left] && colors[i] != colors[right])
                ++cnt;
        }
        return cnt;
    }
};

class Solution3 {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> st(nums.begin(), nums.end());

        for (auto& num : st)
        {
            int cur = num;
            if (!st.count(cur - 1))
            {
                int len = 1;
                while (st.count(cur + 1))
                {
                    ++len;
                    ++cur;
                }
                res = max(res, len);
            }
        }

        return res;
    }
};

class Solution4 {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) return false;
        int cnt[26] = { 0 };
        for (int c : magazine) ++cnt[c - 'a'];
        for (int c : ransomNote)
            if (--cnt[c - 'a'] < 0)
                return false;
        return true;
    }
};

class Solution5 {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        ListNode dummy = ListNode(-1);
        ListNode* tail = &dummy;
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if (list1) tail->next = list1;
        if (list2) tail->next = list2;
        return dummy.next;
    }
};

class Solution6 {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k) {
        int n = colors.size();
        int cnt = 0; int cur = 0;
        for (int i = 0; i < n * 2; ++i)
        {
            if (i && colors[i % n] == colors[(i - 1) % n])
                cur = 0;
            ++cur;
            if (cur >= k && i >= n)
                ++cnt;
        }
        return cnt;
    }
};

class Solution7 {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        unordered_set<ListNode*> st;
        while (headA)
        {
            st.insert(headA);
            headA = headA->next;
        }
        while (headB)
        {
            if (!st.count(headB))
                st.insert(headB);
            else
                return headB;
            headB = headB->next;
        }
        return nullptr;
    }
};